package com.wzy.sort8;

import java.util.Arrays;

/**
 * @author wzy
 * @Date: 2022/1/30 15:04
 * @Description: 堆排序  二叉树
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] nums = {5, 1, 8, 2, 6, 7, 3, 4};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    /**
     * 堆排序
     *
     * @param arr
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        /*for (int i = 0; i < arr.length; i++) { // O(N)
            heapInsert(arr ,i);//O(logn)
        }*/
        // 如果只是为了构建大根堆  这个方法更快
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    /**
     * 构建大根堆 依次向根节点比较 向上移动
     *
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 某个数在index位置 是否需要向下移动
     *
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1; // 左孩子的下标
        while (left < heapSize) { // 下方有孩子的时候
            int large = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //父和较大孩子之间 谁的值大，把下标给large
            large = arr[large] > arr[index] ? large : index;
            if (large == index) {
                break;
            }
            swap(arr, large, index);
            index = large;
            left = 2 * index + 1;
        }
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
